翻訳と辞書 Words near each other ・ Segrià ・ Segro ・ Segrois ・ Segismundo Moret ・ Segizinchi Mart ・ Seglora ・ Segment ・ Segment (handwriting) ・ Segment (linguistics) ・ Segment 3 ・ Segment addition postulate ・ Segment architecture ・ Segment descriptor ・ Segment polarity gene ・ Segment protection ・ Segment tree ・ Segmental analysis (biology) ・ Segmental arteries of kidney ・ Segmental blood pressure ・ Segmental bridge ・ Segmental duplication ・ Segmental innervation ・ Segmental medullary artery ・ Segmental odontomaxillary dysplasia ・ Segmental resection ・ Segmental stabilizers ・ Segmentary lineage ・ Segmentation ・ Segmentation (biology) ・ Segmentation and Reassembly Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Segment tree ： ウィキペディア英語版 Segment tree In computer science, a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its structure cannot be modified once it is built. A similar data structure is the interval tree. A segment tree for a set ''I'' of ''n'' intervals uses O(''n'' log ''n'') storage and can be built in O(''n'' log ''n'') time. Segment trees support searching for all the intervals that contain a query point in O(log ''n'' + ''k''), ''k'' being the number of retrieved intervals or segments. Applications of the segment tree are in the areas of computational geometry, and geographic information systems. The segment tree can be generalized to higher dimension spaces as well. ==Structure description== ''This section describes the structure of a segment tree in a one-dimensional space.'' Let ''S'' be a set of intervals, or segments. Let ''p''1, ''p''2, ..., ''pm'' be the list of distinct interval endpoints, sorted from left to right. Consider the partitioning of the real line induced by those points. The regions of this partitioning are called ''elementary intervals''. Thus, the elementary intervals are, from left to right: :$(-\backslash infty,\; p\_1),\; (),\; (p\_1,\; p\_2),\; (p\_2),\; ...,\; (p\_,\; p\_m),\; (p\_m),\; (p\_m,\; +\backslash infty)$ That is, the list of elementary intervals consists of open intervals between two consecutive endpoints ''pi'' and ''p''''i''+1, alternated with closed intervals consisting of a single endpoint. Single points are treated themselves as intervals because the answer to a query is not necessarily the same at the interior of an elementary interval and its endpoints. Given a set ''I'' of intervals, or segments, a segment tree ''T'' for ''I'' is structured as follows: * ''T'' is a binary tree. * Its leaves correspond to the elementary intervals induced by the endpoints in ''I'', in an ordered way: the leftmost leaf corresponds to the leftmost interval, and so on. The elementary interval corresponding to a leaf ''v'' is denoted Int(''v''). * The internal nodes of ''T'' correspond to intervals that are the union of elementary intervals: the interval Int(''N'') corresponding to node ''N'' is the union of the intervals corresponding to the leaves of the tree rooted at ''N''. That implies that Int(''N'') is the union of the intervals of its two children. * Each node or leaf ''v'' in ''T'' stores the interval Int(''v'') and a set of intervals, in some data structure. This canonical subset of node ''v'' contains the intervals (''x′'' ) from ''I'' such that (''x′'' ) contains Int(''v'') and does not contain Int(parent(''v'')). That is, each node in ''T'' stores the segments that span through its interval, but do not span through the interval of its parent. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Segment tree」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.